<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>KMP</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="kmp">KMP</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=GTJr8OvyEVQ&amp;list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de&amp;index=4">https://www.youtube.com/watch?v=GTJr8OvyEVQ&amp;list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de&amp;index=4</a></li>
<li><a href="https://github.com/labuladong/fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B9%8BKMP%E5%AD%97%E7%AC%A6%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95.html">https://github.com/labuladong/fucking-algorithm/blob/master/动态规划系列/动态规划之KMP字符匹配算法.md</a></li>
</ul>
<p>关于next数组的计算原理可以参考下面的视频</p>
<ul>
<li><a href="https://www.youtube.com/watch?v=KG44VoDtsAA&amp;list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de&amp;index=3">https://www.youtube.com/watch?v=KG44VoDtsAA&amp;list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de&amp;index=3</a></li>
</ul>
<h1 id="1-labuladong">1. labuladong</h1>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">prepare</span><span class="hljs-params">(pattern)</span>:</span>   
    <span class="hljs-string">''' 计算动态矩阵mat, 公共前缀commonA, KMP的nextA数组'''</span>
    
    n = len(pattern)
    mat = []
    mat.append(defaultdict(int))
    mat[<span class="hljs-number">0</span>][pattern[<span class="hljs-number">0</span>]] = <span class="hljs-number">1</span>

    commonA = [<span class="hljs-number">0</span>]
    X = <span class="hljs-number">0</span>
    <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n):
        new_state = deepcopy(mat[X]) <span class="hljs-comment"># 注意，这里是deepcopy(mat[X]), 不是 deepcopy(mat[-1])</span>
        new_state[pattern[i]] = i+<span class="hljs-number">1</span>
        mat.append(new_state)
        X = mat[X][pattern[i]]
        commonA.append(X)


    nextA = [<span class="hljs-number">-1</span>] + commonA[:<span class="hljs-number">-1</span>]
    <span class="hljs-keyword">return</span> mat, commonA, nextA

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">search</span><span class="hljs-params">(text, pattern, mat)</span>:</span>
    <span class="hljs-string">''' 使用动态矩阵来查找'''</span>
    n = len(pattern)
    m = len(text)

    j = <span class="hljs-number">0</span>
    <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m):
        j = mat[j][text[i]]
        <span class="hljs-keyword">if</span> j == n:
            <span class="hljs-keyword">return</span> i - n + <span class="hljs-number">1</span>
    <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">search2</span><span class="hljs-params">(text, pattern, next)</span>:</span>
    <span class="hljs-string">''' 使用next数组来查找'''</span>
    i = <span class="hljs-number">0</span>
    j = <span class="hljs-number">0</span>
    <span class="hljs-keyword">while</span> i &lt; len(text) <span class="hljs-keyword">and</span> j &lt; len(pattern):
        <span class="hljs-keyword">if</span> j==<span class="hljs-number">-1</span> <span class="hljs-keyword">or</span> text[i] == pattern[j]:
            i += <span class="hljs-number">1</span>
            j += <span class="hljs-number">1</span>
        <span class="hljs-keyword">else</span>:
            j = next[j]

    <span class="hljs-keyword">if</span> j == len(pattern):
        <span class="hljs-keyword">return</span> i - len(pattern)
    <span class="hljs-keyword">else</span>:
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>

</div></code></pre>
<p>关于next 数组和公共前缀commonA的关系</p>
<pre><code><code><div>pattern = &quot;qwqq&quot;
commonA=[0, 0, 1, 1] nextA=[-1, 0, 0, 1]

pattern = &quot;qqqq&quot;
commonA=[0, 1, 2, 3] nextA=[-1, 0, 1, 2]

</div></code></code></pre>
<h1 id="2-lc-214-shortest-palindrome">2. LC 214. Shortest Palindrome</h1>
<ul>
<li><a href="https://leetcode.com/problems/shortest-palindrome/">https://leetcode.com/problems/shortest-palindrome/</a></li>
</ul>
<p>Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.</p>
<pre><code><code><div>Example 1:

Input: &quot;aacecaaa&quot;
Output: &quot;aaacecaaa&quot;

Example 2:

Input: &quot;abcd&quot;
Output: &quot;dcbabcd&quot;
</div></code></code></pre>
<p>本题本质上是求， find the longest palindrome substring starts from 0.</p>
<p>We can solve it by using a trick + KMP.</p>
<p>The trick is to build a temp string like this:</p>
<p>s + &quot;#&quot; + reverse(s)</p>
<p>Then we run KMP on it, the value in last cell will be our solution. In this problem, we don't need to use KMP
to match strings but instead we use the lookup table in KMP to find the palindrome.</p>
<p>Example:</p>
<p>input:</p>
<pre><code>catacb
</code></pre>
<p>Temp String:</p>
<pre><code>catacb # bcatac
</code></pre>
<p>KMP table:(这里是公共前缀数组，不是KMP的next数组)</p>
<pre><code>c a t a c b # b c a t a c
0 0 0 0 1 0 0 0 1 2 3 4 5
</code></pre>
<p>In the last cell, we got a value 5. It means in s we have a substring of length 5 that is palindrome.</p>
<p>下面是我的代码</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict
<span class="hljs-keyword">from</span> copy <span class="hljs-keyword">import</span> deepcopy
<span class="hljs-keyword">from</span> pprint <span class="hljs-keyword">import</span> pprint

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">shortestPalindrome</span><span class="hljs-params">(self, s: str)</span> -&gt; str:</span>
        
        s2 = s + <span class="hljs-string">"#"</span> + s[::<span class="hljs-number">-1</span>]
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(pattern)</span>:</span>
            n = len(pattern)
            mat = []
            d = defaultdict(int)
            d[pattern[<span class="hljs-number">0</span>]] = <span class="hljs-number">1</span>
            mat.append(d)
            X = <span class="hljs-number">0</span>
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n):
                c = pattern[i]
                d2 = deepcopy(mat[X])
                d2[c] = i + <span class="hljs-number">1</span>
                mat.append(d2)
                X = mat[X][c]
            <span class="hljs-keyword">return</span> X
        
        X = _helper(s2)
        <span class="hljs-keyword">return</span> s[X:][::<span class="hljs-number">-1</span>] + s
             
</div></code></pre>
<h1 id="3-lc-459-repeated-substring-pattern">3. LC 459. Repeated Substring Pattern</h1>
<ul>
<li><a href="https://leetcode.com/problems/repeated-substring-pattern/">https://leetcode.com/problems/repeated-substring-pattern/</a></li>
</ul>
<p>Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.</p>
<pre><code><code><div>Example 1:

Input: &quot;abab&quot;
Output: True
Explanation: It's the substring &quot;ab&quot; twice.

Example 2:

Input: &quot;aba&quot;
Output: False

Example 3:

Input: &quot;abcabcabcabc&quot;
Output: True
Explanation: It's the substring &quot;abc&quot; four times. (And the substring &quot;abcabc&quot; twice.)
</div></code></code></pre>
<h2 id="解法1">解法1</h2>
<p>借助KMP思想，找到公共前缀 s1, 然后验证原始数组s 是由s1构成的即可。</p>
<h2 id="解法2">解法2</h2>
<p>很诡异，不容易想到</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">repeatedSubstringPattern</span><span class="hljs-params">(self, s: str)</span> -&gt; bool:</span>
        <span class="hljs-keyword">return</span> s <span class="hljs-keyword">in</span> (<span class="hljs-number">2</span> * s)[<span class="hljs-number">1</span>:<span class="hljs-number">-1</span>]
</div></code></pre>
<h1 id="4-lc-1392-longest-happy-prefix">4. LC 1392. Longest Happy Prefix</h1>
<ul>
<li><a href="https://leetcode.com/problems/longest-happy-prefix/">https://leetcode.com/problems/longest-happy-prefix/</a></li>
</ul>
<p>A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).</p>
<p>Given a string s. Return the longest happy prefix of s .</p>
<p>Return an empty string if no such prefix exists.</p>
<pre><code><code><div>
Example 1:

Input: s = &quot;level&quot;
Output: &quot;l&quot;
Explanation: s contains 4 prefix excluding itself (&quot;l&quot;, &quot;le&quot;, &quot;lev&quot;, &quot;leve&quot;), and suffix (&quot;l&quot;, &quot;el&quot;, &quot;vel&quot;, &quot;evel&quot;). The largest prefix which is also suffix is given by &quot;l&quot;.
Example 2:

Input: s = &quot;ababab&quot;
Output: &quot;abab&quot;
Explanation: &quot;abab&quot; is the largest prefix which is also suffix. They can overlap in the original string.
</div></code></code></pre>
<h2 id="kmp-1">KMP</h2>
<p>本题就是求公共前缀， 但是用KMP算法，提交会超时</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict
<span class="hljs-keyword">from</span> copy <span class="hljs-keyword">import</span> deepcopy

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestPrefix</span><span class="hljs-params">(self, s: str)</span> -&gt; str:</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(s)</span>:</span>
            mat = [defaultdict(int)]
            n = len(s)
            mat[<span class="hljs-number">0</span>][s[<span class="hljs-number">0</span>]] = <span class="hljs-number">1</span>
            X = <span class="hljs-number">0</span>
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n):
                new_state = deepcopy(mat[X])
                new_state[s[i]] = i+<span class="hljs-number">1</span>
                mat.append(new_state)
                X = mat[X][s[i]]
            <span class="hljs-keyword">return</span> X
        
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper2</span><span class="hljs-params">(pat)</span>:</span>
            nexta = [<span class="hljs-number">-1</span>] + [<span class="hljs-number">0</span>] * len(pat) 
            commona = [<span class="hljs-number">0</span>] * len(pat)
            i = <span class="hljs-number">0</span>
            j = <span class="hljs-number">-1</span>
            <span class="hljs-keyword">while</span> i &lt; len(pat):
                <span class="hljs-keyword">if</span> j == <span class="hljs-number">-1</span> <span class="hljs-keyword">or</span> pat[i] == pat[j]:
                    commona[i] = j+<span class="hljs-number">1</span>
                    i += <span class="hljs-number">1</span>
                    j += <span class="hljs-number">1</span>
                    nexta[i] = j
                <span class="hljs-keyword">else</span>:
                    j = nexta[j]
            <span class="hljs-keyword">return</span> commona[<span class="hljs-number">-1</span>]

        
        X = _helper(s)
        <span class="hljs-keyword">return</span> s[:X]
    
</div></code></pre>
<h2 id="rolling-hash">Rolling Hash</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestPrefix</span><span class="hljs-params">(self, s)</span>:</span>
        <span class="hljs-comment"># res stores the index of the end of the prefix, used for output the result</span>
        <span class="hljs-comment"># l stores the hash key for prefix</span>
        <span class="hljs-comment"># r stores the hash key for suffix</span>
        <span class="hljs-comment"># mod is used to make sure that the hash value doesn't get too big, you can choose another mod value if you want.</span>
        res, l, r, mod = <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">10</span>**<span class="hljs-number">9</span> + <span class="hljs-number">7</span>

        <span class="hljs-comment"># now we start from the beginning and the end of the string</span>
        <span class="hljs-comment"># note you shouldn't search the whole string! because the longest prefix and suffix is the string itself</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(s) - <span class="hljs-number">1</span>):

            <span class="hljs-comment"># based on an idea that is similar to prefix sum, we calculate the prefix hash in O(1) time.</span>
            <span class="hljs-comment"># specifically, we multiply the current prefix by 128 (which is the length of ASCII, but you can use another value as well)</span>
            <span class="hljs-comment"># then add in the ASCII value of the upcoming letter</span>
            l = (l * <span class="hljs-number">128</span> + ord(s[i])) % mod

            <span class="hljs-comment"># similarly, we can calculate the suffix hash in O(1) time.</span>
            <span class="hljs-comment"># Specifically, we get the ith letter from the end using s[~i], note ~i is -i-1</span>
            <span class="hljs-comment"># we find the pow(128, i, mod) and multiply by the letter's ASCII value</span>
            <span class="hljs-comment"># Actually, if we don't care about the beautifulness of the code, you can have a variable to keep track of pow(128, i, mod) as you increase i</span>
            r = (r + pow(<span class="hljs-number">128</span>, i, mod) * ord(s[~i])) % mod

           <span class="hljs-comment"># we check if the prefix and suffix agrees, if yes, we find yet another longer prefix, so we record the index</span>
            <span class="hljs-keyword">if</span> l == r: res = i + <span class="hljs-number">1</span>

       <span class="hljs-comment"># after we finish searching the string, output the prefix</span>
        <span class="hljs-keyword">return</span> s[:res]
</div></code></pre>
<p>滚动hash的题目还可以参考 LC 1044. Longest Duplicate Substring</p>
<ul>
<li><a href="https://leetcode.com/problems/longest-duplicate-substring/">https://leetcode.com/problems/longest-duplicate-substring/</a></li>
</ul>

    </body>
    </html>